Parts · Full · Next ▶

top

Intuitively, an algorithmically random sequence (or random sequence) is a sequence of binary digits that appears random to any algorithm running on a (prefix-free or not) universal Turing machine. The notion can be applied analogously to sequences on any finite alphabet (e.g. decimal digits). Random sequences are key objects of study in algorithmic information theory.

In measure-theoretic probability theory, introduced by Andrey Kolmogorov in 1933, there is no such thing as a random sequence. For example, consider flipping a fair coin infinitely many times. Any particular sequence, be it 0000 … … {\displaystyle 0000\dots } or 011010 … … {\displaystyle 011010\dots } , has equal probability of exactly zero. There is no way to state that one sequence is "more random" than another sequence, using the language of measure-theoretic probability. However, it is intuitively obvious that 011010 … … {\displaystyle 011010\dots } looks more random than 0000 … … {\displaystyle 0000\dots } . Algorithmic randomness theory formalizes this intuition.

Parts · Full · Next ▶